package backtrack;
import java.util.*;
public class _01_77_组合 {
	List<List<Integer>> list = new ArrayList<List<Integer>>();
	List<Integer> item = new ArrayList<Integer>();

    public List<List<Integer>> combine(int n, int k) {
    	// 1-n所有可能的k个数的组合
    	backtracking(n,k,1);
//    	System.out.println(list.size());
//    	for (List<Integer> l1 : list) {
//			for (Integer integer : l1) {
//				System.out.print(integer + " ");
//			}
//			System.out.println();
//		}
    	
    	return list;
    }
    
	public void backtracking(int n, int k,int startIndex) {
		// 当元素个数等于要求个数k时，则存储并返回
		if(item.size() == k) {
			// 必须是new，否则记录到的是全局item的地址，在其它地方remove时，item里面的时也会被remove
			list.add(new ArrayList(item));
			return;
		}
		
		for(int i = startIndex; i <= n; i++) {
			// 将当前i放入
			item.add(i);
			// 搜索下一个值
			backtracking(n, k, i + 1);
			// 搜索完说明元素满足个数了，撤回新增的元素
			item.remove(item.size() - 1);
		}
		
	}
	public static void main(String[] args) {
		_01_77_组合 a = new _01_77_组合();
		a.combine(1, 1);
	}
}
